package com.leetcode.algorithm.y18.m05;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import com.leetcode.algorithm.common.ListNode;

/**
 * leetcode-cn.com
 * 203. 删除链表中的节点
 * 204. 计数质数
 * 205. 同构字符串
 * 206. 反转链表
 * 217. 存在重复元素
 * 219. 存在重复元素 II
 * 231. 2的幂
 * @author: jie.deng
 * @time: 2018年5月10日 上午9:16:08
 */
public class MySolution0510 {
	
	/**
	 * 203. 删除链表中的节点
	 * 删除链表中等于给定值 val 的所有节点。 
	 * 
	 * 示例:
	 * 输入: 1->2->6->3->4->5->6, val = 6 
	 * 输出: 1->2->3->4->5
	 * @param head
	 * @param val
	 * @return
	 * @date:  2018年5月10日
	 */
    public ListNode removeElements(ListNode head, int val) {
		ListNode ret = new ListNode(0);
		ret.next = head;
		ListNode pre = ret;
		ListNode cur = head;
		while (cur != null) {
			if (cur.val == val) {
				pre.next = cur.next;
			}else {
				pre = pre.next;
			}
			cur = cur.next;
		}
		return ret.next;
    }
    
    /**
	 * 205. 同构字符串 
	 * 给定两个字符串 s 和 t，判断它们是否是同构的。
	 * 如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
	 * 所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
	 * 
	 * 示例 1:
	 * 输入: s = "egg", t = "add" 
	 * 输出: true 
	 * 
	 * 示例 2:
	 * 输入: s = "foo", t = "bar" 
	 * 输出: false 
	 * 
	 * 示例 3:
	 * 输入: s = "paper", t = "title" 
	 * 输出: true 
	 * 
	 * 说明: 你可以假设 s 和 t 具有相同的长度。
	 * 
	 * @param s
	 * @param t
	 * @return
	 */
    public boolean isIsomorphic(String s, String t) {
		if ((s == null && t != null) || (t == null && s != null)) {
			return false;
		}
		if (s.length() != t.length()) {
			return false;
		}
		Map<Character, Character> sMap = new HashMap<Character, Character>();
		Set<Character> tSet = new HashSet<Character>();
		for (int i = 0; i < s.length(); i++) {
			char charS = s.charAt(i);
			char charT = t.charAt(i);
			if (sMap.containsKey(charS)) {
				if (!sMap.get(charS).equals(charT)) {
					return false;
				}
			} else {
				if (tSet.contains(charT)) {
					return false;
				} else {
					sMap.put(charS, charT);
					tSet.add(charT);
				}
			}
		}
		return true;
    }
	
	/**
	 * 204. 计数质数
	 * 统计所有小于非负数整数 n 的质数的数量。
	 * 
	 * 示例:
	 * 输入: 10 
	 * 输出: 4 
	 * 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
	 * 
	 * @param n
	 * @return
	 */
	public int countPrimes(int n) {
		if (n < 2) {
			return 0;
		}
		boolean[] flagArr = new boolean[n];
		Arrays.fill(flagArr, true);
		flagArr[0] = false; // ret[0]代表0，不是质数
		flagArr[1] = false; // ret[0]代表1，不是质数
		for (int num = 2; num * num <= n; num++) {
			if (flagArr[num]) {
				for (int j = num * num; j < n; j += num) {
					flagArr[j] = false;

				}
			}
		}
		int cnt = 0;
		for (int i = 2; i < n; i++) {
			if (flagArr[i]) {
				cnt++;
			}
		}
		return cnt;
	}
	
	/**
	 * 206. 反转链表
	 * 反转一个单链表。
	 * 
	 * 示例:
	 * 输入: 1->2->3->4->5->NULL 
	 * 输出: 5->4->3->2->1->NULL 
	 * 
	 * 进阶:
	 * 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
	 * 
	 * @param head
	 * @return
	 */
    public ListNode reverseList(ListNode head) {
		ListNode ret = null;
		ListNode h = head;
		while (h != null) {
			ListNode cur = h;
			h = h.next;
			cur.next = ret;
			ret = cur;
		}
		return ret;
    }
    
    
    /**
	 * 217. 存在重复元素
	 * 给定一个整数数组，判断是否存在重复元素。
	 * 如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
	 * 
	 * 示例 1:
	 * 输入: [1,2,3,1] 
	 * 输出: true 
	 * 
	 * 示例 2:
	 * 输入: [1,2,3,4] 
	 * 输出: false 
	 * 
	 * 示例 3:
	 * 输入: [1,1,1,3,3,4,3,2,4,2] 
	 * 输出: true
	 * 
	 * @param nums
	 * @return
	 */
    public boolean containsDuplicate(int[] nums) {
		Set<Integer> set = new HashSet<Integer>();
		for (int i = 0; i < nums.length; i++) {
			int num = nums[i];
			if (set.contains(num)) {
				return true;
			} else {
				set.add(num);
			}
		}
		return false;
    }
    
    /**
	 * 219. 存在重复元素 II
	 * 
	 * 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j
	 * 的差的绝对值最大为 k。
	 * 
	 * 示例 1:
	 * 输入: [1,2,3,1], k = 3 
	 * 输出: true 
	 * 
	 * 示例 2:
	 * 输入: [1,0,1,1], k = 1 
	 * 输出: true 
	 * 
	 * 示例 3:
	 * 输入: [1,2,1], k = 0 
	 * 输出: false
	 * 
	 * @param nums
	 * @param k
	 * @return
	 */
	public boolean containsNearbyDuplicate(int[] nums, int k) {
		if (k == 0 || nums.length < 2) {
			return false;
		}
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();// key为nums[i],value=i
		for (int i = 0; i < nums.length; i++) {
			int num = nums[i];
			Integer idx = map.get(num);
			if (idx != null && i - idx <= k) {
				return true;
			} else {
				map.put(num, i); // map不含num时新增，包含时更新索引值。
			}
		}
		return false;
	}
    
    /**
	 * 231. 2的幂
	 * 给定一个整数，写一个函数来判断它是否是 2 的幂次方。
	 * 
	 * 示例 1:
	 * 输入: 1 
	 * 输出: true 
	 * 
	 * 示例 2:
	 * 输入: 16 
	 * 输出: true 
	 * 
	 * 示例 3:
	 * 输入: 218 
	 * 输出: false
	 * 
	 * @param n
	 * @return
	 */
	public boolean isPowerOfTwo(int n) {
		while (n >= 2) {
			if (n % 2 == 1) {
				return false;
			}
			n = n / 2;
		}
		return n == 1;
	}
	public boolean isPowerOfTwoSolution(int n) {
		return (n > 0) && (n & (n - 1)) == 0;
	}
    
}
